/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2025-09-22
 * Time: 14:25
 */
public class ThirdHashMap<K,V> {


    // 内部节点类
    class Node<K,V>{
        private K key;
        private V value;

        private Node<K,V> next;

        public Node(K key,V value){
            this.key = key;
            this.value = value;
        }

        public Node(K key,V value,Node<K,V> next){
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    // 默认容量
    private int DEFAULT_CAPACITY = 16;
    // 负载因子
    private float LOAD_FACTOR = 0.75f;
    // 哈希表大小
    private int size ;
    // 桶数组
    Node<K,V>[] buckets;

    // 无参的就设置未默认容量
    public ThirdHashMap(){
        buckets = new Node[DEFAULT_CAPACITY];
        size = 0;
    }

    // 有参就设置为传递过来的参数
    public ThirdHashMap(int capacity){
        buckets = new Node[capacity];
        size = 0;
    }

    // 哈希函数：获取地址
    private int getIndex(K key,int length){
        int hashCode = key.hashCode();
        int index = hashCode % length;
        return Math.abs(index);
    }

    // put方法
    public void put(K key,V value){
        // 是否需要扩容
        if(size>= buckets.length*LOAD_FACTOR){
            // 扩容
            resize();
        }
        putVal(key,value,buckets);
    }

    // 扩容
    private void resize() {
        Node<K,V>[] newBuckets = new Node[buckets.length*2];
        rehash(newBuckets);
        buckets = newBuckets;
    }

    // 再哈希
    private void rehash(Node<K, V>[] newBuckets) {
        size = 0;
        for(int i=0;i< buckets.length;i++){
            if (buckets[i]==null){
                continue;
            }
            Node<K,V> node = buckets[i];
            while(node!=null){
                putVal(node.key, node.value, newBuckets);
                node = node.next;
            }
        }
    }

    // 放入元素
    private void putVal(K key, V value, Node<K, V>[] table) {
        int index = getIndex(key,table.length);
        Node node = table[index];
        if(node==null){
            table[index] = new Node<>(key,value);
            size++;
            return;
        }
        while (node!=null){
            // 同一个元素
            if((node.key.hashCode()==key.hashCode()) && (node.key.equals(key))){
                node.value = value;
                return;
            }
            node = node.next;
        }
        Node newNode = new Node(key,value,table[index]);
        table[index] = newNode;
        size++;
    }

    // 获取元素
    public V get(K key){
        int index = getIndex(key,buckets.length);
        if(buckets[index]==null){
            return null;
        }
        Node<K,V> node = buckets[index];
        while(node!=null){
            if((node.key.hashCode()==key.hashCode()) && (node.key.equals(key))){
                return node.value;
            }
            node = node.next;
        }
        return null;
    }


    // 获取长度
    public int getSize(){
        return size;
    }

}
